package 算法.leetcode.bytedance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lchenglong
 * @date 2022/5/9
 */
public class OfferArray_I {

    public static void main(String[] args) {
        OfferArray_I instance = new OfferArray_I();
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        instance.threeSum(nums);
    }
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int a = 0;a<n;a++){
            // 需要和上次枚举的数不一样
            if (a>0 && nums[a]==nums[a-1])continue;
            // c为数组的最右端
            int c = n-1;
            int target = -nums[a];
            // 枚举 b
            for (int b = a+1;b<n;b++) {
                // 需要和上一次枚举的数不相同
                if (b>a+1 && nums[b]==nums[b-1])continue;
                // 需要保证 b 的指针在 c 的指针的左侧
                while (b<c&&nums[b]+nums[c]>target){
                    --c;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (b==c)break;
                if (nums[b]+nums[c] == target){
                    List<Integer> subAns =new ArrayList<>();
                    subAns.add(nums[a]);
                    subAns.add(nums[b]);
                    subAns.add(nums[c]);
                    ans.add(subAns);
                }
            }
        }
        return ans;
    }
}
